/*
1926. 迷宫中离入口最近的出口
https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
中等 2024/12/04
*/

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int n=maze.size();
        int m=maze[0].size();
        int k=entrance[0]*m+entrance[1];
        queue<pair<int,int>>q;
        q.push({k,0});
        while(!q.empty())
        {
            auto it=q.front();
            int t=it.first;
            int ans=it.second;
            q.pop();
            int x=t/m,y=t%m;
            maze[x][y]='+';
            vector<pair<int,int>>arr={{-1,0},{1,0},{0,-1},{0,1}};
            for(int i=0;i<4;i++)
            {
                int a=arr[i].first,b=arr[i].second;
                if(x+a>n-1||x+a<0||y+b>m-1||y+b<0)
                continue;
                if(maze[x+a][y+b]=='.')
                {
                    if(x+a==0||y+b==0||x+a==n-1||y+b==m-1) return ans+1;
                    int z=(x+a)*m+y+b;
                    maze[x+a][y+b]='+';
                    q.push({z,ans+1});
                }
                
            }
        }
        return -1;
    }
};